package exams.dp;

import java.security.InvalidParameterException;
import java.util.*;

public class PathSolution {

    /**
     * 不同路径的数目
     *
     * 一个机器人在m×n大小的地图的左上角（起点）。
     * 机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
     * 可以有多少种不同的路径从起点走到终点？
     *
     * 备注：m和n小于等于100,并保证计算结果在int范围内
     * 数据范围：0<n,m≤100，保证计算结果在32位整型范围内
     * 要求：空间复杂度O(nm)，时间复杂度O(nm)
     * 进阶：空间复杂度O(1)，时间复杂度O(min(n,m))
     * */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(i == 0 || j == 0){
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j-1] + dp[i-1][j];
                }
            }
        }

        return dp[m - 1][n - 1];
    }

    /**
     * 矩阵的最小路径和
     *
     * 给定一个n * m的矩阵a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
     * 数据范围:1≤n,m≤500矩阵中任意值都满足0≤ai,j≤100
     * 要求：时间复杂度O(nm)
     * 例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
     *
     * 输入：
     * [[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
     * 返回值：
     * 12
     * */
    public int minPathSum (int[][] matrix) {
        // write code here
        int n = matrix.length;
        if(n == 0) {
            return 0;
        }
        int m = matrix[0].length;
        if(m == 0) {
            return 0;
        }

        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        for(int i =1; i<= n; i++) {
            for(int j = 1; j<=m; j ++) {
                if(i == 1) {
                    dp[i][j] = dp[i][j - 1] + matrix[i - 1][j - 1];
                } else if(j == 1) {
                    dp[i][j] = dp[i-1][j] + matrix[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i-1][j]) + matrix[i - 1][j - 1];
                }
            }
        }

        return dp[n][m];
    }

    /**
     * 兑换零钱(一)
     *
     * 给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
     * 如果无解，请返回-1.
     * 数据范围：数组大小满足0≤n≤10000， 数组中每个数字都满足0<val≤10000，0≤aim≤5000
     * 要求：时间复杂度O(n×aim)，空间复杂度O(aim)。
     * */
    public int minMoney (int[] arr, int aim) {
        if(aim == 0) {
            return 0;
        }
        int[] dp = new int[aim + 1];
        Arrays.fill(dp, aim+1);
        dp[0] = 0;

        for(int i =1; i<= aim; i++) {
            for(int j =0; j<arr.length; j++) {
                if(arr[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1);
                }
            }
        }

        return dp[aim]>aim?-1:dp[aim];
    }

    /**
     * 编辑距离(一)
     *
     * 给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。
     * 你可以对字符串进行3种操作：
     * 1.插入一个字符
     * 2.删除一个字符
     * 3.修改一个字符。
     *
     * 字符串长度满足1≤n≤1000，保证字符串中只出现小写英文字母。
     * */
    public int editDistance (String str1, String str2) {
        // write code here
        int len1 = str1.length();
        int len2 = str2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        int maxDpLen = 0;
        for(int i=1;i<=len1; i++) {
            dp[i][0] = dp[i-1][0] + 1;
        }
        for(int i=1; i<=len2; i++) {
            dp[0][i] = dp[0][i-1] + 1;
        }

        for(int i = 1; i <= str1.length(); i++) {
            for(int j = 1; j <= str2.length(); j ++) {
                if(str1.charAt(i-1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }

    /**
     * 打家劫舍(一)
     *
     * 你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
     * 给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
     *
     * 数据范围：数组长度满足1≤n≤2×105，数组中每个值满足1≤num[i]≤5000
     * */
    public int rob (int[] nums) {
        // write code here
        int[] dp = new int[nums.length  + 1];
        dp[1] = nums[0];

        for(int i =2; i<=nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }

        return dp[nums.length];
    }

    /**
     * 打家劫舍(二)
     *
     * 你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
     * 给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
     *
     * 数据范围：数组长度满足1≤n≤2×105，数组中每个值满足1≤nums[i]≤5000
     * */
    public int rob2 (int[] nums) {
        // write code here
        int res = 0;
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];

        for(int i=2; i<nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        res = dp[nums.length - 1];

        dp[1] = 0;
        dp[2] = nums[1];
        for(int i =3; i<=nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
        }
        res = Math.max(res, dp[nums.length]);

        return res;
    }

    /**
     * 买卖股票的最好时机(一)
     *
     * 假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
     * 1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
     * 2.如果不能获取到任何利润，请返回0
     * 3.假设买入卖出均无手续费
     *
     * 数据范围：0≤n≤105,0≤val≤104
     * 要求：空间复杂度O(1)，时间复杂度O(n)
     * */
    public int maxProfit (int[] prices) {
        // write code here
        int res = 0;
        int minP = prices[0];

        for(int i=1;i<prices.length;i++) {
            if(prices[i] > minP) {
                res = Math.max(res, prices[i] - minP);
            } else {
                minP = prices[i];
            }
        }

        return res;
    }

    /**
     * 买卖股票的最好时机(二)
     *
     * 假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
     * 1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
     * 2. 如果不能获取收益，请返回0
     * 3. 假设买入卖出均无手续费
     *
     * 数据范围：1≤n≤1×105，1≤prices[i]≤104
     * 要求：空间复杂度O(n)，时间复杂度O(n)
     * 进阶：空间复杂度O(1)，时间复杂度O(n)
     *
     * 输入：
     * [8,9,2,5,4,7,1]
     * 返回值：
     * 7
     * 说明：
     * 在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
     * 在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
     * 在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
     * 总获利1+3+3=7，返回7
     * */
    public int maxProfit2 (int[] prices) {
        // write code here
        // 不持有股票收益状态
        int[] dp0 = new int[prices.length];
        // 持有股票收益状态
        int[] dp1 = new int[prices.length];
        dp0[0] = 0;
        dp1[0] = -prices[0];

        for(int i=1; i<prices.length; i++) {
            dp0[i] = Math.max(dp0[i - 1], dp1[i - 1] + prices[i]);
            dp1[i] = Math.max(dp1[i - 1], dp0[i -1]-prices[i]);
        }

        return Math.max(dp0[prices.length -1], dp1[prices.length -1]);
    }

    /**
     * 买卖股票的最好时机(三)
     *
     * 假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
     * 1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
     * 2. 如果不能获取收益，请返回0
     * 3. 假设买入卖出均无手续费
     *
     * 数据范围：1≤n≤105，股票的价格满足1≤val≤104
     * 要求:空间复杂度O(n)，时间复杂度O(n)
     * 进阶：空间复杂度O(1)，时间复杂度O(n)
     * */
    public int maxProfit3 (int[] prices) {
        // write code here
        int[] operations = {-1, 1, -1, 1};
        int[][] dp = new int[prices.length][operations.length + 1];
        Arrays.fill(dp[0], -10000);
        dp[0][0] = 0;
        dp[0][1] = prices[0] * operations[0];

        for(int i = 1; i< prices.length; i++) {
            for(int j =1; j <= operations.length; j++) {
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1] + prices[i]*operations[j - 1]);
            }
        }

        return Math.max(dp[prices.length - 1][2], Math.max(0, dp[prices.length -1][4]));
    }


}
